package example3;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class LeetCode215 {
    public static void main(String[] args) {
        int[] arr = {3,2,1,5,6,4};
//        Arrays.sort(arr);
        System.out.println(new Solution215().findKthLargest(arr,2));
//        new Solution().quicklySort(arr,0,5);
//        System.out.println(Arrays.toString(arr));
//        List<Integer> list = Arrays.asList(arr);
//        Collections.sort(list);
//        System.out.println(list);
    }
}

class Solution215 {
    //-----------------------------------------------------------------
    //方法3：官方给的堆排序，比快排慢一些
    public int findKthLargest(int[] nums, int k) {
        int heapSize = nums.length;
        buildMaxHeap(nums, heapSize);
        for (int i = nums.length - 1; i >= nums.length - k + 1; --i) {
            swap(nums, 0, i);
            --heapSize;
            maxHeapify(nums, 0, heapSize);
        }
        return nums[0];
    }

    public void buildMaxHeap(int[] a, int heapSize) {
        for (int i = heapSize / 2 - 1; i >= 0; --i) {
            maxHeapify(a, i, heapSize);
        }
    }

    public void maxHeapify(int[] a, int i, int heapSize) {
        int l = i * 2 + 1, r = i * 2 + 2, largest = i;
        if (l < heapSize && a[l] > a[largest]) {
            largest = l;
        }
        if (r < heapSize && a[r] > a[largest]) {
            largest = r;
        }
        if (largest != i) {
            swap(a, i, largest);
            maxHeapify(a, largest, heapSize);
        }
    }

    public void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    //-----------------------------------------------------------------
    //方法二：官方给的快排，性能极好
    public int findKthLargest2(int[] _nums, int k) {
        int n = _nums.length;
        return quickselect(_nums, 0, n - 1, n - k);
    }

    int quickselect(int[] nums, int l, int r, int k) {
        if (l == r) return nums[k];
        int x = nums[l], i = l - 1, j = r + 1;
        while (i < j) {
            do i++; while (nums[i] < x);
            do j--; while (nums[j] > x);
            if (i < j){
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }
        }
        if (k <= j) return quickselect(nums, l, j, k);
        else return quickselect(nums, j + 1, r, k);
    }


    //-----------------------------------------------------------------
    //方法一：我写的快排，交换次数过多，性能极差
    public int findKthLargest1(int[] nums, int k) {
//        Arrays.sort(nums);
//        quicklySort(nums,0,nums.length-1);
        return quicklySelect(nums,0,nums.length-1,nums.length - k);
    }

    public int quicklySelect(int[] nums,int low,int high,int k){
        int l = low;
        int h = high;
        if(low >= high) return nums[k];
        int temp = nums[low];
        while(low < high){
            while(nums[high] >= temp && low < high){
                high--;
            }
            nums[low] = nums[high];
            nums[high] = temp;
            while(nums[low] <= temp && low < high){
                low++;
            }
            nums[high] = nums[low];
            nums[low] = temp;
        }
        if(k >= low){
            return quicklySelect(nums,low+1,h,k);
        }else{
            return quicklySelect(nums,l,low-1,k);
        }
    }

    //{3,2,1,5,6,4}
    public void quicklySort(int[] nums,int low,int high){
        int l = low;
        int h = high;
        if(low >= high) return;
        int temp = nums[low];
        while(low < high){
            while(nums[high] >= temp && low < high){
                high--;
            }
            nums[low] = nums[high];
            nums[high] = temp;
            while(nums[low] <= temp && low < high){
                low++;
            }
            nums[high] = nums[low];
            nums[low] = temp;
        }
        quicklySort(nums,l,low-1);
        quicklySort(nums,low+1,h);
    }
}
